package com.jacklei.tree;
//平衡二叉树
public class BalancedBinaryTree {

    static class Node {
        int value;
        Node left;
        Node right;

        public Node(int value) {
            this.value = value;
        }
    }

    static class Result{
        int high;
        boolean balanced;

        public Result(int high, boolean balanced) {
            this.high = high;
            this.balanced = balanced;
        }
    }

    public static void main(String[] args) {
        Node root = new Node(1);

        root.left = new Node(2);
        root.right = new Node(3);

        root.left.left = new Node(4);
        root.left.right = new Node(5);

        root.right.left = new Node(6);
        root.right.right = new Node(7);
        System.out.println(checkBalanced(root));
    }
    //判断是否为平衡二叉树
    public static boolean checkBalanced(Node root){
        return balanced(root).balanced;
    }

    public static Result balanced(Node root) {
        if(root == null) {
            return new Result(0,true);
        }

        Result left = balanced(root.left);
        Result right = balanced(root.right);

        Result result = new Result(-1,false);

        if (!left.balanced || !right.balanced){
            return result;
        }

        result.high = Math.max(left.high, right.high)+ 1;

        if(Math.abs(left.high - right.high) <= 1){
            result.balanced = true;
        }else {
            result.balanced = false;
        }

            return result;
    }
}
